/*后缀数组
    n个后缀 O(nlogn) 将所有后缀按字典序排序

* 1.sa[] 倍增求sa[]
    sa[i]表示数组中排名第i的数组下标
    rank[i]第i个后缀的排名是多少

    设置一个桶c[i]表示值为i的数的数量，
    先将所有后缀子串按第一个字符排序，基数排序是稳定的，
    当第一个字符相等时不会改变原后缀子串的顺序，
    每次排序按长度排序，长度不足后面用字典序最小的字符补齐，
    例如前一次倍增排好了长度为k的子串，此时排序长度为 2×k 的子串，
    由于基数排序的稳定性，整体上可以将长度为 2×k 的子串先将后 k 个字符排序，再将前 k 个字符排序，
    这样可以保证对于长度为 2×k 的子串来说，前 k 个子串相等，后 k 个子串也会是排好序的，
    这样长度为 2×k 的子串就排好了序，同时可求解sa[]

* 2.height[]
    height[i]表示sa[i]和sa[i-1]的最长公共前缀

    先定义函数 lcp(i,j):表示排名为i和j的最长公共前缀，
    则有 lcp(i,j)=min(lcp(i,k),lcp(k,j))，其中 i<j
 再定义数组 height[i]表示下标为 i 的后缀和排名为 sa[i]−1 的后缀的最长公共前缀，则有 h[i]≥h[i−1]−1

*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define DEBUG
inline int read()
{
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x;
}
inline void write(int x)
{
	if (x>=10) write(x/10);
	putchar(x%10+48);
}//快读快输

const int N=1e6+10;
int n,m,cnt,c[N],x[N],y[N],sa[N],rk[N],height[N];
/*
c[]:桶排序的计数数组
x[],y[]:存储临时的排名信息
sa[]:后缀数组 表示数组中排名第i的后缀的数组下标
rk[]:排名数组 第i个后缀的排名是多少
height[]:高度数组 表示sa[i]和sa[i-1]的最长公共前缀
*/
char str[N];

void getsa()
{
    for(int i=1; i<=n; i++) c[x[i]=str[i]]++; //每个字符作为一个初始的排名
    for(int i=2; i<=m; i++) c[i]+=c[i-1]; //前缀和计算
    for(int i=n; i>=1; i--) sa[c[x[i]]--]=i; //根据字符的排名进行桶排
                            //c[x[i]]--:下一个相同排名的元素会放入前一个位置，保证相同元素的相对顺序不变
    //倍增 求sa[]
    for(int k=1; k<=n; k<<=1) //每次比较长度k 翻倍
    {
        //以i为起始位置，向后走k长度
        cnt=0;
        for(int i=n-k+1; i<=n; i++) y[++cnt]=i;//后缀长度不足k的先放入y数组
        //后缀长度不足k的不具备在本轮划分排序的第二关键字，根据之前的排名信息排序    
        
        for(int i=1; i<=n; i++) 
            if(sa[i]>k) y[++cnt]=sa[i]-k; //后缀长度足够k的后缀根据上一轮排名放入y数组
        
        //在此桶排序，更新sa[]
        //x[i]:以i为起始位置的后缀在当前轮次的排名
        //y[i]:下一轮排序时第i个要处理的后缀(以y[i]为起始位置的后缀)的起始位置(按照y[]中存储的顺序进行排序)
        for(int i=1; i<=m; i++) c[i]=0; //上一轮比较的前缀和清零重新计算
        for(int i=1; i<=n; i++) c[x[i]]++; //每个后缀作为初始排名
        for(int i=2; i<=m; i++) c[i]+=c[i-1];

        //根据当前后缀排名，上一轮记录的排序顺序 进行桶排
        for(int i=n; i>=1; i--) sa[c[x[y[i]]]--]=y[i], y[i]=0; //根据y[](处理顺序)和x[](上一轮的排序顺序)进行桶排
        
        //为下一轮比较做准备
        swap(x, y);
        //此时 x[]是下一轮排序时后缀的顺序信息 y[]是当前轮次排名 x[sa[i]]是排名为i的后缀在当前轮次的排名
        x[sa[1]]=1, cnt=1; //更新x[](当前轮次中各个后缀的排名信息),统计不同排名的数量
        //上一轮排名为1的，这一轮排名仍为1
        for(int i=2; i<=n; i++)
            x[sa[i]]=(y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k])?cnt:++cnt;
        //相邻两个后缀 在上一轮的前半部分(比较前k个字符) 和 后半部分(从起始位置偏移k个位置后的部分)的排名
        //均若相同->两个后缀在当前轮次的大小关系仍然相同，则在新一轮排名也相同，否则排名+1
        //x[]是排名
        if(cnt==n) break;
        m=cnt;
        
    }
}

void getheight()
{
    for(int i=1; i<=n; i++) rk[sa[i]]=i; //根据后缀数组更新排名数组
    for(int i=1, k=0; i<=n; i++) //遍历每个位置
    {
        if(rk[1]==1) continue; //排名为1的后缀没有前一个后缀
        if(k) k--; //利用上一次的最长公共前缀长度进行优化
        int j=sa[rk[i]-1]; //找到排名为rk[i]-1的后缀的起始位置
        while(i+k<=n && str[i+k]==str[j+k]) k++; //计算当前后缀和前一个后缀的最长公共前缀长度
        height[rk[i]]=k; //记录最长公共前缀长度到高度数组中
    }
}

void solve()
{
    scanf("%s", str+1);
    n=strlen(str+1);
    m='z';
    getsa();
    getheight();

    for(int i=1; i<=n; i++) printf("%d ", sa[i]);
    puts("");
    for(int i=1; i<=n; i++) printf("%d ", height[i]);
    puts("");
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
        freopen("./out.txt","w",stdout);
    #endif

    
    int T=1; //T=read();
    while(T--)
    {
        solve();
    }
    return 0;
}
